package com.fengye.algorithms.leecode.dp;

/**
 * 给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
 *
 * 返回 你可以获得的最大乘积 。
 *
 * @Author fengye
 * @Date 2023/5/7 9:03
 **/
public class IntegerBreak343 {

    public static void main(String[] args) {
        System.out.println(new IntegerBreak343().integerBreak(4));
    }

    /**
     * 每个数最大乘积取决与比它小的数的最大乘积
     *
     * 当 i≥2 时，假设对正整数i 拆分出的第一个正整数是 j（1≤j<i），则有以下两种方案：
     *
     * 将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j×(i−j)；
     *
     * 将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j×dp[i−j]。
     *
     * @param n
     * @return
     */
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        for(int i=2;i<=n;i++) {
            int max = 0;
            for(int j=1;j<i;j++) {
                max = Math.max(max, Math.max(j*(i-j), j*dp[i-j]));
            }
            dp[i] = max;
        }
        return dp[n];
    }

    public int integerBreak1(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(Math.max(2 * (i - 2), 2 * dp[i - 2]), Math.max(3 * (i - 3), 3 * dp[i - 3]));
        }
        return dp[n];
    }

    /**
     * 数学归纳法
     * @param n
     * @return
     */
    public int integerBreak2(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int quotient = n / 3;
        int remainder = n % 3;
        if (remainder == 0) {
            return (int) Math.pow(3, quotient);
        } else if (remainder == 1) {
            return (int) Math.pow(3, quotient - 1) * 4;
        } else {
            return (int) Math.pow(3, quotient) * 2;
        }
    }

}
